#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from util_tree import *
from sys import maxsize as MAX_INT


# class TreeNode:
#     def __init__(self, val):
#         self.val = val
#         self.left, self.right = None, None


class Solution:
    def removeNode(self, root, value):
        dummy_root = TreeNode(MAX_INT)
        dummy_root.left = root

        parent, node = self.find_value_parent_node(dummy_root, value)

        if not node:
            # 没有找到value(包括root为None的情况)
            return root

        if node.val < parent.val:
            parent.left = self.remove_node(node)
        else:
            parent.right = self.remove_node(node)

        return dummy_root.left

    def find_value_parent_node(self, root, value):
        # return (parent, node)
        parent = root
        node = root

        while node:
            node_save = node
            if value < node.val:
                node = node.left
            elif value > node.val:
                node = node.right
            else:
                # print('here')
                # print(node.val)
                # print(parent.val)
                assert value == node.val
                break

            # 在最后更新parent
            parent = node_save

        return parent, node

    def remove_node(self, node):
        # 删除node节点

        if node.left is None:
            return node.right

        if node.right is None:
            return node.left

        # 寻找node的排序前驱节点
        successor_parent, successor = self.find_most_right_and_parent(node.left, node)
        if successor is node.left:
            # node的前驱节点是node.left(即node.left没有right节点)
            # successor.left不变
            # assert successor_parent is node
            successor.right = node.right
            return successor

        # 找到successor
        print('successor %s' % successor.val)
        assert successor_parent.right is successor
        successor_parent.right = successor.left     # 记得处理successor_parent.right, 并且这里不是None, 而是前驱节点的left
        # successor_parent.right = None
        successor.left, successor.right = node.left, node.right
        return successor

    def find_most_right_and_parent(self, node, parent):
        # find node's rightest node
        rightest = node

        while rightest.right:
            parent = rightest
            rightest = rightest.right

        return parent, rightest


    # def rec_remove_node(self, node):
    #     if node.left and node.right:
    #         slot = node.left
    #         slot.left = self.rec_remove_node(slot)
    #         slot.right = node.right
    #         return slot
    #     else:
    #         # None or None is None
    #         slot = node.left or node.right
    #         return slot


def main():
    print("start main")

    s = Solution()

    root = build_tree_from_str('3,#,20')
    ret = s.removeNode(root, 3)
    ret.show()

    root = build_tree_from_str('10,5,20,3,8,15,30,1,4,#,#,#,#,#,#')
    root.show()
    ret = s.removeNode(root, 5)
    ret.show()

    root = build_tree_from_str('10,5,20,3,8,15,30,1,4,6,#,#,#,#,#')
    root.show()
    ret = s.removeNode(root, 10)
    ret.show()

if __name__ == "__main__":
    main()
